package day_2022_4_to_7.nowcoder;

/**
 * 合并两个排序的链表
 * @author haomin
 * @date 2022/04/16 10:43
 **/
public class Merge_13f {
    // 方法一
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        ListNode dummyNode = new ListNode(-1);
        // 定义一个last节点，指向新链表的末节点位置
        ListNode last = dummyNode;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                // 将list1节点 接在last 后
                last.next = list1;
                // 更新末尾节点位置
                last = list1;
                // 头结点后移一位
                list1 = list1.next;
            }else {
                // 将list2节点 接在last 后
                last.next =list2;
                // 更新末尾节点位置
                last = list2;
                // 头结点后移一位
                list2 = list2.next;
            }
        }

        if(list1 == null){
            //如果list1 空了，直接接list2链
            last.next = list2;
        }
        if(list2 == null){
            //如果list2 空了，直接接list1链
            last.next = list1;
        }
        return dummyNode.next;
    }

    // 递归
    public ListNode Merge2(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        if(list1.val < list2.val){
            list1.next = Merge2(list1.next,list2);
            // 如果list1.val < list2.val，list2头结点之后就接list1
            return list1;
        }else {
            list2.next = Merge2(list1,list2.next);
            // 反之，list1头结点就接list2
            return list2;
        }
    }
}